package LearnAlgorithm.d_标准查找算法and标准排序算法;

public class b5a快速排序by单项扫描分区方式plus三点中值优化 {
	public static void main(String[] args) {
//		int[] arr = new int[] {6,8,7,9,5,4,3};
//		int[] arr = new int[] {7,2,3,5,9,9,9};
		int[] arr = new int[] {9,8,7,6,5,4,3,2,1};
		
		long before = System.currentTimeMillis();
		quickSort(arr, 0, arr.length-1);
		util.Util.duration(before);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
//	public static void quickSortMy(int[] arr, int p, int r) {
//		if (p < r) {
//			int q = partitionMy(arr, p, r);
//			quickSortMy(arr, p, q-1);
//			quickSortMy(arr, q+1, r);
//		}
//	}
	
	/**
	 * 快速排序
	 * O(NlogN)
	 * @param arr
	 * @param p
	 * @param r
	 */
	public static void quickSort(int[] arr, int p, int r) {//使用递归
		if (p < r) {
			int q = partition(arr, p, r);//核心语句在这行，即找出主元
			quickSort(arr, p, q-1);//对主元左边排序
			quickSort(arr, q+1, r);//对主元右边排序
		}
	}
	

//	public static int partitionMy(int[] arr, int p, int r) {
//		int threeMidValueIndex = threeMidValue(arr, p, r, p + ((r - p) >>> 1));
//		int pivot = arr[threeMidValueIndex];
//		while (p < r) {
//			if (arr[p] <= pivot) {
//				p++;
//			} else {
//				swap(arr, p, r);
//				r--;
//			}
//		}
////		swap(arr, threeMidValueIndex, r);
//		return r;
//	}
	
	/**
	 * 三点找中值
	 * @param arr
	 * @param p
	 * @param r
	 * @param mid
	 * @return
	 */
	public static int threeMidValue(int[] arr, int p, int r, int mid) {
		int midValueIndex = -1;//该片段的“中值”的对应的下标，至于这个“中值”它到底有多少程度的“中”，其实很难说，这也是三点中值法的痛。
		if ((arr[mid] >= arr[p] && arr[p] >= arr[r]) || (arr[r] >= arr[p] && arr[p] >= arr[mid])) {
			midValueIndex = p;//p就是----该片段的“中值”的对应的下标
		} else if ((arr[mid] >= arr[r] && arr[r] >= arr[p]) || (arr[p] >= arr[r] && arr[r] >= arr[mid])) {
			midValueIndex = r;//r就是----该片段的“中值”的对应的下标
		} else {
			midValueIndex = mid;//midIndex就是----该片段的“中值”的对应的下标
		}
		return midValueIndex;
	}
	
	/**
	 * 交换值方法
	 * @param arr
	 * @param i
	 * @param j
	 */
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	
	/**
	 * 快速排序核心---设置主元并把主元放在相对居中的位置
	 * 同时使用了优化，三点中值优化
	 * 单项扫描基本用的不多，重点在于“三点中值优化”
	 * 老师的思想---主元是首值
	 * 自己的思想在单项扫描上有问题。不改了，浪费时间他妈的。反正竞赛和商业也不用单项扫描。
	 * @param arr
	 * @param p
	 * @param r
	 * @return bigger
	 */
	public static int partition(int[] arr, int p, int r) {
		//三点优化：在p,r,midIndex之间，选一个中间值作为主元，它们仨在数值大小上都有可能是中间值
		int midIndex = p + ((r - p) >>> 1);//传入partition的数组片段的该片段的中间索引
		int midValueIndex = -1;//该片段的“中值”的对应的下标，至于这个“中值”它到底有多少程度的“中”，其实很难说，这也是三点中值法的痛。
		if (arr[midIndex] >= arr[p] && arr[p] >= arr[r]) {
			midValueIndex = p;//p就是----该片段的“中值”的对应的下标
		} else if (arr[midIndex] >= arr[r] && arr[r] >= arr[p]) {
			midValueIndex = r;//r就是----该片段的“中值”的对应的下标
		} else {
			midValueIndex = midIndex;//midIndex就是----该片段的“中值”的对应的下标
		}
		swap(arr, p, midValueIndex);////把三点中值与首值进行交换，因为主要工作核心语句是以首值为对比对象开发的，我也可以把主要工作核心语句更新迭代，但是费时间，所以这里直接交换了
		int pivot = arr[p];//定义主元pivot
		//下面是主要工作核心语句
		int sp = p + 1;//定义右移指针
		int bigger = r;//定义左移指针
		while (sp <= bigger) {//当sp>bigger,代表数组全部元素都与主元比对完毕
			if (arr[sp] <= pivot) {//sp指针指向的值，小于主元，仅右移sp
				sp++;
			} else {
				if (sp < bigger) {//为什么要加上<判断；是因为如果sp==bigger时，还去交换arr[sp]与arr[bigger]，是没意义的，加上判断能提升运行效率
					swap(arr, sp, bigger);//sp指针指向的值，大于主元，就把arr[sp]与arr[bigger]交换，再左移bigger
				}
				bigger--;//单向扫描，bigger--不能放进上面的sp < bigger判断中
			}
		}
		/*
		 * 最后跳出循环时，一定一定是bigger指向最后一个小于主元的值
		 * 并且sp指向第一个大于主元的值
		 * 所以只要把arr[p]与arr[bigger]交换，arr[p]左侧一定小于主元，右侧一定大于主元
		 * 这里的一定一定，在视频中已经讲得很清楚了：蓝桥杯第三章3.3快排单项扫描
		 */
		swap(arr, p, bigger);//这里理论上也能改进，如arr[p]==arr[biger],如p==bigger的情况，但是我不改进了，我怕出错
		return bigger;//最后返回主元所在的索引
	}
	
	/***
	 * 快速排序核心
	 * 主元是数组片段首元素
	 * 无优化
	 * @param arr
	 * @param p
	 * @param r
	 * @return bigger
	 */
	public static int partition_old(int[] arr, int p, int r) {
		int pivot = arr[p];//定义主元pivot
		int sp = p+1;//定义右移指针
		int bigger = r;//定义左移指针
		while (sp <= bigger) {//当sp>bigger,代表数组全部元素都与主元比对完毕
			if (arr[sp] <= pivot) {//sp指针指向的值，小于主元，仅右移sp
				sp++;
			} else {
				if (sp != bigger) {//为什么要加上!=判断；是因为如果sp==bigger时，还去交换arr[sp]与arr[bigger]，是没意义的，加上判断能提升运行效率
					swap(arr, sp, bigger);//sp指针指向的值，大于主元，就把arr[sp]与arr[bigger]交换，再左移bigger
				}
				bigger--;
			}
		}
		/*
		 * 最后跳出循环时，一定一定是bigger指向最后一个小于主元的值
		 * 并且sp指向第一个大于主元的值
		 * 所以只要把arr[p]与arr[bigger]交换，arr[p]左侧一定小于主元，右侧一定大于主元
		 * 这里的一定一定，在视频中已经讲得很清楚了：蓝桥杯第三章3.3快排单项扫描
		 */
		swap(arr, p, bigger);//这里理论上也能改进，如arr[p]==arr[biger],如p==bigger的情况，但是我不改进了，我怕出错
		return bigger;//最后返回主元所在的索引
	}
}
